﻿//#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>
//#include <assert.h>
//#include <string.h>
//#include <stdlib.h>

#include "common.h"

size_t my_strlen1(const char* str)
{ // 循环版本
    assert(str); // NULL 值为 0
    char* p = (char*)str;
    while (*str++ != '\0'); // '\0' 值为 0，可以不写
    return (size_t)(str - p - 1); // 减去最后一个 '\0'
}

size_t my_strlen2(const char* str)
{ // 递归的版本，智障才用
    assert(str);
    if ('\0' == *str)
        return (size_t)0;
    else
        return 1 + my_strlen2(str + 1); // 递归调用
}

char* my_strcpy(char* dest, const char* src)
{
    assert(dest && src);
    char* start = dest;
    while (*dest++ = *src++); // 直到遇到 '\0'（会被复制）结束
    return start; // 返回复制的起始地址（目标字符串的首字符地址）
}

char* my_strcpy_n(char* dest, const char* src, size_t n)
{
    assert(dest && src);
    char* start = dest;
    while (n-- > 0)
    {
        if ('\0' != *src)
            *dest++ = *src++; // 直到复制 n 个字符或遇到 '\0'（会被复制）结束
        else
            *dest++ = '\0'; // 超出 src 部分用 '\0' 填充
    }
    return start; // 返回复制的起始地址（目标字符串的首字符地址）
}

char* my_strcat(char* dest, const char* src)
{
    assert(dest && src);
    char* start = dest;
    //while ('\0' != (*dest++)); // 直到遇到 '\0'（会被复制）后，dest + 1 结束
    //*--dest = ' '; // 将 '\0' 替换为 ' '
    //while ('\0' != (*dest++ = *src++)); // 复制剩余的字符串
    while (*dest)
        ++dest; // 找到字符串末尾
    while (*src)
        *dest++ = *src++; // 复制剩余的字符串
    return start; // 返回复制的起始地址（目标字符串的首字符地址）
}

char* my_strcat_n(char* dest, const char* src, size_t n)
{
    assert(dest && src);
    char* start = dest;
    while (*dest)
        ++dest; // 找到字符串末尾
    while (n--) // n = 0 退出循环
    {
        if ('\0' != *src)
            *dest++ = *src++; // 直到复制 n 个字符或遇到 '\0'（会被复制）结束
        else
            break;
    }
    *dest = '\0'; // 字符串末尾追加 '\0'
    return start; // 返回复制的起始地址（目标字符串的首字符地址）
}

int my_strcmp(const char* str1, const char* str2)
{  // 0 表示相同，<0 表示 str1 比 str2 短（字符靠面），>0 表示 str1 比 str2 长（字符靠后）
    assert(str1 && str2);
    /*int i = 0;
    while (str1[i] && str2[i] && str1[i] == str2[i])
        ++i;*/
        //while (*str1 && *str2 && *str1 == *str2)
        //{ // 这里 *str1 == '\0' 直接退出循环
        //    ++str1;
        //    ++str2;
        //}
        //if ('\0' == *str1 && '\0' == *str2)
        //    return 0; // 两个字符串完全相同
        //else if ('\0' == *str1)
        //    return -1; // str1 比 str2 短
        //else if ('\0' == *str2)
        //    return 1; // str1 比 str2 长
        //else
        //    return *str1 > *str2 ? 1 : -1;

     // 优化：
        /*while (*str1 == *str2)
        {
            if ('\0' == *str1)
                return 0; // 两个字符串完全相同
            ++str1;
            ++str2;
        }*/
        // 优化升级版：
    while (*str1 != '\0' && *str2 != '\0' && *str1++ == *str2++); // != '\0' 可不写
    // 说明：这里把与 '\0' 的比较放在前面，防止两字符比较遇到 '\0' 后指针向后偏移
    return *str1 - *str2; // 最后一个字符的差值，小值在前哦
}

int my_strcmp_n(const char* str1, const char* str2, size_t n)
{
    assert(str1 && str2);
    while (n-- > 1 && *str1 && *str2 && *str1++ == *str2++); // 遇到 '\0' 直接退出
    /*if (*str1 == *str2)
        return 0; // 两个字符串前面 n 个字符完全相同
    else*/
    return *str1 - *str2; // 第 n 个字符的差值，小值在前哦
}

void str_compare(const char* str1, const char* str2)
{
    int cmp_result = my_strcmp(str1, str2);
    if (0 == cmp_result)
        printf("str1 is equal to str2.\n");
    else if (cmp_result < 0)
        printf("str1 is less than str2.\n");
    else
        printf("str1 is greater than str2.\n");
}

void str_compare_n(const char* str1, const char* str2, size_t n)
{
    int cmp_result = my_strcmp_n(str1, str2, n);
    if (0 == cmp_result)
        printf("str1 is equal to str2.\n");
    else if (cmp_result < 0)
        printf("str1 is less than str2.\n");
    else
        printf("str1 is greater than str2.\n");
}

char* my_strstr1(const char* str, const char* substr)
{ // 递归版本
    assert(str && substr);
    if (*str == '\0' || !*substr) // !*substr 同 *substr == '\0'
        return NULL; // 空字符串或空子串，返回 NULL
    while (*str && *str != *substr)
        ++str; // 找到 str 开头的位置
    const char* p_str = str; // 保存 str 中 substr 的首字符地址
    const char* p_substr = substr; // 保存 substr 的首字符地址
    while (*str && *substr && *str++ == *substr++);
    if (!*substr) // 找到了
        return (char*)p_str;
    else if (!*p_str || !*str)  // *p_str == '\0' 必写，不然某种 !str 时有 bug
        return NULL; // 没找到，结束
    else
        return my_strstr1(p_str + 1, p_substr); // 递归查找
}

char* my_strstr2(const char* str, const char* substr)
{ // 暴力循环求解版本，时间复杂度 O(n * km) k 一般不计算
    assert(str && substr);
    const char* p_str = str; // 保存 substr 的首字符地址
    while (*str)
    {
        const char* p_substr = substr; // 保存 substr 的首字符地址
        int count = 0;
        while (*substr)
        { // 使得 count 等于 substr 的长度减一
            ++substr;
            ++count;
        }
        substr = p_substr; // 回退 substr 指针
        // 以上 while 循环与回退操作直接使用 strlen 函数
        if (*str == *substr)
        {
            int i;
            p_str = str; // 保存 substr 的首字符地址
            for (i = 1; i < count; ++i)
            {
                if (str[i] != substr[i])
                    break;
                else if (i == count - 1)
                    return (char*)p_str; // 找到了
            }
        }
        ++str;
    }

    /* //鹏哥的版本：
    const char* s1 = NULL;
    const char* s2 = NULL;
    while (*str)
    {
        s1 = str; // 每次循环重置 s1 指针
        s2 = substr; // 每次循环重置 s2 指针
        while (*s1 && *s2 && *s1++ == *s2++);
        if (!*s2)
            return (char*)str;
        else if (!*s1)
            return NULL; // 找完了，没找到，提前结束
        ++str;
    } */
    return NULL; // 没找到
}

// 计算部分匹配表（也叫做前缀表）向 FittenCode 学习代码
void computeLPSArray(char* pat, int M, int* lps)
{ // 计算 pat 位置的前缀与后缀的最长公共子串的长度，并存储在 lps 数组中
    int len = 0; // 前缀的长度
    lps[0] = 0;  // lps[0] 总是 0 这一步很重要

    int i = 1;
    while (i < M)
    {
        if (pat[i] == pat[len])
        {
            ++len;
            lps[i] = len;
            ++i;
        }
        else
            if (len != 0)
                len = lps[len - 1]; // 回退到前一个可能的前缀
            else
            {
                lps[i] = 0;
                ++i;
            }
    }
}

// KMP算法：查找子串（在 txt 中查找 pat）向 FittenCode 学习代码
char* KMPsearch(char* txt, char* pat)
{  // 时间复杂度为 O(n + km) k 一般不计算
    int M = (int)strlen(pat);
    int N = (int)strlen(txt);

    // 创建部分匹配表
    int* lps = (int*)malloc(M * sizeof(int));
    assert(lps); // malloc 失败，退出程序
    computeLPSArray(pat, M, lps);

    int i = 0; // txt的下标
    int j = 0; // pat的下标
    while (i < N)
    {
        if (pat[j] == txt[i])
        {
            ++i;
            ++j;
        }

        if (j == M && lps != NULL)
        {
            //printf("找到模式'%s'在文本中的起始位置: %d\n", pat, i - j);
            //j = (int)lps[j - 1]; // 找到后，回退一步，继续查找（多次查找）
            return txt += i - j; // 返回模式的起始位置
        }
        else if (i < N && pat[j] != txt[i])
            if (j != 0 && lps != NULL)
                j = lps[j - 1]; // 回退
            else
                ++i;
    }
    return NULL; // 没找到
}


